{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sell Diminishing-Valued Colored Balls"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #math #binary-search #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #数学 #二分查找 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxProfit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #销售价值减少的颜色球"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有一些球的库存 <code>inventory</code> ，里面包含着不同颜色的球。一个顾客想要 <strong>任意颜色</strong> 总数为 <code>orders</code> 的球。</p>\n",
    "\n",
    "<p>这位顾客有一种特殊的方式衡量球的价值：每个球的价值是目前剩下的 <strong>同色球</strong> 的数目。比方说还剩下 <code>6</code> 个黄球，那么顾客买第一个黄球的时候该黄球的价值为 <code>6</code> 。这笔交易以后，只剩下 <code>5</code> 个黄球了，所以下一个黄球的价值为 <code>5</code> （也就是球的价值随着顾客购买同色球是递减的）</p>\n",
    "\n",
    "<p>给你整数数组 <code>inventory</code> ，其中 <code>inventory[i]</code> 表示第 <code>i</code> 种颜色球一开始的数目。同时给你整数 <code>orders</code> ，表示顾客总共想买的球数目。你可以按照 <strong>任意顺序</strong> 卖球。</p>\n",
    "\n",
    "<p>请你返回卖了 <code>orders</code> 个球以后 <strong>最大</strong> 总价值之和。由于答案可能会很大，请你返回答案对 <code>10<sup>9</sup> + 7</code> <strong>取余数</strong> 的结果。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/11/08/jj.gif\" style=\"width: 480px; height: 270px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>inventory = [2,5], orders = 4\n",
    "<b>输出：</b>14\n",
    "<b>解释：</b>卖 1 个第一种颜色的球（价值为 2 )，卖 3 个第二种颜色的球（价值为 5 + 4 + 3）。\n",
    "最大总和为 2 + 5 + 4 + 3 = 14 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>inventory = [3,5], orders = 6\n",
    "<b>输出：</b>19\n",
    "<strong>解释：</strong>卖 2 个第一种颜色的球（价值为 3 + 2），卖 4 个第二种颜色的球（价值为 5 + 4 + 3 + 2）。\n",
    "最大总和为 3 + 2 + 5 + 4 + 3 + 2 = 19 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>inventory = [2,8,4,10,6], orders = 20\n",
    "<b>输出：</b>110\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>inventory = [1000000000], orders = 1000000000\n",
    "<b>输出：</b>21\n",
    "<strong>解释：</strong>卖 1000000000 次第一种颜色的球，总价值为 500000000500000000 。 500000000500000000 对 10<sup>9 </sup>+ 7 取余为 21 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= inventory.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= inventory[i] <= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 <= orders <= min(sum(inventory[i]), 10<sup>9</sup>)</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sell-diminishing-valued-colored-balls](https://leetcode.cn/problems/sell-diminishing-valued-colored-balls/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sell-diminishing-valued-colored-balls](https://leetcode.cn/problems/sell-diminishing-valued-colored-balls/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,5]\\n4', '[3,5]\\n6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        inventory.sort(reverse=True)\n",
    "        ans = 0\n",
    "        for i, x in enumerate(inventory):\n",
    "            diff = x - (inventory[i + 1] if i + 1 < len(inventory) else 0)\n",
    "            prefix_length = i + 1\n",
    "            time = min(diff, orders // prefix_length)\n",
    "            # x - time + 1 ... x\n",
    "            ans += prefix_length * (x - time + 1 + x) * time // 2\n",
    "            x -= time\n",
    "            orders -= prefix_length * time\n",
    "            diff -= time\n",
    "            if orders > 0:\n",
    "                for v in range(x, x - diff, -1):\n",
    "                    if orders == 0:\n",
    "                        break\n",
    "                    ans += min(prefix_length, orders) * v\n",
    "                    orders -= min(prefix_length, orders)\n",
    "\n",
    "        return int(ans) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        n = len(inventory) \n",
    "        inventory.sort() \n",
    "        def check(k):\n",
    "            tot = 0 \n",
    "            for i in range(n):\n",
    "                tot += max(inventory[i] - k + 1, 0)\n",
    "            return tot >= orders\n",
    "        \n",
    "        l, r = 0, inventory[-1]\n",
    "        while l< r:\n",
    "            mid = (l + r+1)>>1\n",
    "            if check(mid):\n",
    "                l = mid \n",
    "            else:\n",
    "                r = mid - 1\n",
    "        tot = 0  \n",
    "        for i in range(n):\n",
    "            tot += max(inventory[i] - l + 1, 0)\n",
    "        d = tot - orders \n",
    "        ans = -d * l \n",
    "        Mod = int(1e9+7)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if inventory[i] >= l:\n",
    "                ans += (inventory[i] - l+1) * (inventory[i] + l) // 2\n",
    "                if ans > Mod:\n",
    "                    ans %= Mod \n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        mod=10**9+7\n",
    "        def cal(u,h,w):\n",
    "            # 用于计算卖出矩形可以获得的价值\n",
    "            return h*(u+u-h+1)*w//2\n",
    "        inventory.append(0)\n",
    "        inventory.sort()\n",
    "        cur=len(inventory)-1\n",
    "        wid=1\n",
    "        ans=0\n",
    "        while cur>0:\n",
    "            while inventory[cur]==inventory[cur-1]:\n",
    "                # 跳过的部分都当前的最大值，都是可以卖的\n",
    "                cur-=1\n",
    "                wid+=1\n",
    "            upper=inventory[cur]\n",
    "            lower=inventory[cur-1]\n",
    "            # 可以卖出的数额不足 (upper - lower) * width 这个矩形\n",
    "            if orders<(upper-lower)*wid:\n",
    "                h=orders//wid\n",
    "                ans+=cal(upper,h,wid)+((orders-h*wid)*(upper-h))\n",
    "                ans%=mod\n",
    "                break\n",
    "            ans+=cal(upper,upper-lower,wid)\n",
    "            ans%=mod\n",
    "            orders-=(upper-lower)*wid\n",
    "            wid+=1\n",
    "            cur-=1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        # for i in range(len(inventory)):\n",
    "        #     inventory[i]=-inventory[i]\n",
    "        # heapify(inventory)\n",
    "        # ans,mod=0,10**9+7\n",
    "        # while orders and inventory:\n",
    "        #     num1=heappop(inventory)\n",
    "        #     if inventory:\n",
    "        #         num2=heappop(inventory)\n",
    "        #         if orders>=-(num1-num2)+1:\n",
    "        #             ans+=(-((num1+num2)*(num2-num1+1)//2))%mod\n",
    "        #             orders-=(num2-num1+1)\n",
    "        #             heappush(inventory,num2+1)\n",
    "        #             heappush(inventory,num2)\n",
    "        #         else:\n",
    "        #             ans+=(orders*(-num1-num1-orders+1)//2)%mod\n",
    "        #             orders=0\n",
    "        #     else:\n",
    "        #         if orders<-num1:#剩余一种颜色的球，\n",
    "        #             ans+=(orders*(-num1-num1-orders+1)//2)%mod\n",
    "        #         else:\n",
    "        #             ans+=(-num1*(-num1+1)//2)%mod\n",
    "                \n",
    "        #         orders=0\n",
    "        mod,ans=10**9+7,0\n",
    "        l,r,T=0,max(inventory),-1\n",
    "        while l<=r:\n",
    "            mid=(l+r)//2\n",
    "            total=sum([num-mid for num in inventory if num>=mid])\n",
    "            if(total<=orders):\n",
    "                T=mid\n",
    "                r=mid-1\n",
    "            else:\n",
    "                l=mid+1\n",
    "        \n",
    "        range_sum=lambda x,y:(x+y)*(y-x+1)//2\n",
    "        rest=orders-sum(ai-T for ai in inventory if ai>=T)\n",
    "        for num in inventory:\n",
    "            if num>=T:\n",
    "                if rest:\n",
    "                    ans+=range_sum(T,num)\n",
    "                    rest-=1\n",
    "                else:\n",
    "                    ans+=range_sum(T+1,num)\n",
    "        return ans%mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        a = inventory\n",
    "        l, r = 1, max(a)\n",
    "        mod = 10**9 + 7\n",
    "        rs = lambda x, y: (y - x + 1) * (x + y) // 2\n",
    "        while l < r:\n",
    "            m = l + r >> 1\n",
    "            s = sum(x - m for x in a if x > m)\n",
    "            if s <= orders:\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        left = orders - sum(x - l for x in a if x > l) \n",
    "        # print(f'left = {left}, l = {l}')\n",
    "        ans = 0\n",
    "        for x in a:\n",
    "            if x >= l:\n",
    "                if left:\n",
    "                    left -= 1\n",
    "                    ans += rs(l, x)\n",
    "                else:\n",
    "                    ans += rs(l + 1, x)\n",
    "        return ans % mod\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        def check(m):\n",
    "            return sum(max(0,n-m) for n in inventory)\n",
    "\n",
    "        l,r=0,max(inventory)\n",
    "        while l<r:\n",
    "            m=(l+r)//2\n",
    "            if check(m)>orders: l=m+1\n",
    "            else: r=m\n",
    "\n",
    "        cnt,res=0,0\n",
    "        for n in inventory:\n",
    "            if n>l:\n",
    "                cur=n-l\n",
    "                cnt+=cur\n",
    "                res+=cur*(n+l+1)//2\n",
    "        res+=l*(orders-cnt)\n",
    "        return res%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        inventory.sort(reverse = True)\n",
    "        inventory.append(0)\n",
    "        MOD = 10**9 + 7\n",
    "        ans = 0\n",
    "        for i, v  in enumerate(inventory):\n",
    "            j = i + 1\n",
    "            #print(i, orders, j, v)\n",
    "            c = v - inventory[j]\n",
    "            \n",
    "            if orders > j * c:\n",
    "                orders -= j * c\n",
    "                ans += (inventory[j] + v + 1) * c // 2 * j\n",
    "                ans %= MOD\n",
    "                continue\n",
    "            \n",
    "            t = v - orders // j\n",
    "            #print(t, orders, j)\n",
    "            #print(ans)\n",
    "            ans += orders % j * (t + v) * (v - t + 1) // 2 + (j - orders % j) * (t + 1 + v) * (v - t) // 2\n",
    "            #print((j - orders % j) , (t + 1 + v) , (v - t))\n",
    "            return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        # 二分查找 T 值\n",
    "        l, r, T = 0, max(inventory), None\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            total = sum(ai - mid for ai in inventory if ai >= mid)\n",
    "            if total <= orders:\n",
    "                T = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "\n",
    "        range_sum = lambda x, y: (x + y) * (y - x + 1) // 2\n",
    "        print(T)\n",
    "        rest = orders - sum(ai - T for ai in inventory if ai >= T)\n",
    "        ans = 0\n",
    "        for ai in inventory:\n",
    "            if ai >= T:\n",
    "                ans += range_sum(T + 1, ai)\n",
    "                    \n",
    "        return (ans + rest * T) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        # 二分查找 T 值\n",
    "        l, r, T = 0, max(inventory), None\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            total = sum(ai - mid for ai in inventory if ai >= mid)\n",
    "            if total <= orders:\n",
    "                T = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "\n",
    "        range_sum = lambda x, y: (x + y) * (y - x + 1) // 2\n",
    "        print(T)\n",
    "        rest = orders - sum(ai - T for ai in inventory if ai >= T)\n",
    "        ans = 0\n",
    "        for ai in inventory:\n",
    "            if ai >= T:\n",
    "                ans += range_sum(T + 1, ai) % mod\n",
    "                    \n",
    "        return (ans + rest * T) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "贪心 + 二分\n",
    "1. 二分范围为： 0 ~ max(inventory)\n",
    "2. 如果只取大于等于 m 的个数的球，总和 >= orders，则改方案可行，增大 m\n",
    "3. 找到最大的 m 后，计算答案\n",
    "4. 注意：取的时候，需要先取完 > m 的球，剩下的个数就是需要的 = m 的球\n",
    "         如果直接取 >= m 的球，可能就取多了 = m 的球\n",
    "'''\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        mx = max(inventory)\n",
    "\n",
    "        # 找到最大的 m\n",
    "        def check(m):\n",
    "            sm = sum(max(0, x-m+1) for x in inventory)\n",
    "            return sm >= orders\n",
    "\n",
    "        l, r = 0, mx\n",
    "        while l <= r:\n",
    "            m = (l + r + 1) // 2\n",
    "            if check(m):\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "        ans = 0\n",
    "        cnt = orders\n",
    "        # 先取完 > m 的球，剩下的个数就是需要的 = m 的球\n",
    "        for x in inventory:\n",
    "            if x > r:\n",
    "                cnt -= x - r\n",
    "                ans += (x+1)*x//2 - (r+1)*r//2\n",
    "        # 剩下的个数 cnt 就是需要的 = m 的球\n",
    "        return (ans + cnt * r) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        '''\n",
    "        有一个值T，满足当 inventory[i] >=T时，会有 T 或 T - 1 次被去除；\n",
    "        且对于所有大于T的的元素 sum( inventory[i] - T ) < order < sum( inventory[i] - T +1)。\n",
    "        所以，可以通过二分查找找到数值T。\n",
    "\n",
    "        对于 order - sum( inventory[i] - T ) 个球，他们的得分都是都是 T\n",
    "\n",
    "        '''\n",
    "\n",
    "        mod=10**9+7\n",
    "\n",
    "        l,r,T = 0,max(inventory),-1\n",
    "\n",
    "        while l<=r:\n",
    "            mid=(l+r)//2\n",
    "            total = sum( ai - mid   for ai in inventory if ai>=mid )\n",
    "            if total <= orders:\n",
    "                T=mid  #保留最接近的T值，此时，total <=orders\n",
    "                r=mid-1\n",
    "            else:\n",
    "                l=mid+1\n",
    "\n",
    "        rest = orders - sum(ai - T  for ai in inventory if ai>T)\n",
    "        ans=0\n",
    "\n",
    "        range_sum = lambda x, y: (x + y) * (y - x + 1) // 2\n",
    "        for ai in inventory:\n",
    "            if ai>T:\n",
    "                ans+=range_sum(T+1,ai)\n",
    "        if rest>0:\n",
    "            ans += rest*T\n",
    "\n",
    "        return ans % mod\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        # 用于计算卖出矩形可以获得的价值\n",
    "        def calc_matrix(u: int, h: int, w: int) -> int:\n",
    "            return h * (u + u - h + 1) * w // 2\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        # 先排序 inventory，这里插入个零可以避免边界判断\n",
    "        inventory.append(0)\n",
    "        inventory.sort()\n",
    "        self.count = 0\n",
    "        now = len(inventory) - 1\n",
    "        width = 1\n",
    "        while now > 0:\n",
    "            # 跳过的部分都当前的最大值，都是可以卖的\n",
    "            while inventory[now - 1] == inventory[now]:\n",
    "                now -= 1\n",
    "                width += 1\n",
    "\n",
    "            upper = inventory[now]\n",
    "            lower = inventory[now - 1]\n",
    "            # 可以卖出的数额不足 (upper - lower) * width 这个矩形\n",
    "            if orders < (upper - lower) * width:\n",
    "                h = orders // width\n",
    "                self.count += calc_matrix(upper, h, width) + ((orders - h * width) * (upper - h))\n",
    "                self.count %= mod\n",
    "                break\n",
    "            self.count += calc_matrix(upper, upper - lower, width)\n",
    "            self.count %= mod\n",
    "            orders -= (upper - lower) * width\n",
    "            width += 1\n",
    "            now -= 1\n",
    "        return self.count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        # 二分最后达到的最低数量，能够满足orders的数量\n",
    "        # 每种颜色的花费是等差数列求和\n",
    "        MOD = 10**9+7\n",
    "        n = len(inventory)\n",
    "\n",
    "        def check(k):\n",
    "            temp = sum([(inventory[i] - k) for i in range(n) if inventory[i]>k])\n",
    "            return temp>=orders\n",
    "\n",
    "        l,r = 0,max(inventory)\n",
    "        low = -1\n",
    "        while l<=r:\n",
    "            mid = (l+r)//2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "\n",
    "        buy_num = sum([(inventory[i] - low) for i in range(n) if inventory[i]>low])\n",
    "        cost = sum([(inventory[i]+low+1)*(inventory[i]-low)//2 for i in range(n) if inventory[i]>low])\n",
    "        diff = (buy_num - orders)*(low+1)\n",
    "        cost -= diff\n",
    "        return cost%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        #首先肯定是卖多的球\n",
    "        #卖到所有颜色球数量都是最后一个时开始按顺序各卖一个\n",
    "        #先排序，再计算差值,按顺序\n",
    "        #这个通过率感觉会卡超时\n",
    "        inventory.sort(key=lambda x:-x)\n",
    "        inventory.append(0) #如果所有颜色都能出现就把0也考虑上\n",
    "        n=len(inventory)\n",
    "        color,res=1,0 #当前的颜色数,价值数\n",
    "        for i in range(n-1):\n",
    "            num=inventory[i]-inventory[i+1]\n",
    "            print(res,num)\n",
    "            if(orders>num*color): #如果orders够用\n",
    "                #所有颜色球从inventory[i]的价格减到inventory[i+1]\n",
    "                res+=(color*(num)*(inventory[i]+inventory[i+1]+1))//2\n",
    "                orders-=(num)*color\n",
    "            else:\n",
    "                basic=[orders//color,orders%color] #分别存放基础数量和多出数量\n",
    "                #所有球都减到inventory[i]-basic[0]的价位,还有basic[1]在减一个数\n",
    "                #print(orders,color,basic)\n",
    "                res+=color*basic[0]*(2*inventory[i]-basic[0]+1)//2+basic[1]*(inventory[i]-basic[0])\n",
    "                orders=0\n",
    "            if(orders==0):\n",
    "                break\n",
    "            color+=1\n",
    "        return res % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        inventory.sort(reverse=True)\n",
    "        inventory.append(0)\n",
    "        ans = 0\n",
    "        for i in range(len(inventory) - 1):\n",
    "            # print(f\"%d, %d, %d\" % (i + 1, orders, ans))\n",
    "            if inventory[i] > inventory[i + 1]:\n",
    "                tmp = (i + 1) * (inventory[i] + inventory[i + 1] + 1) * (inventory[i] - inventory[i + 1]) // 2\n",
    "                if (inventory[i] - inventory[i + 1]) * (i + 1) < orders:\n",
    "                    orders -= (inventory[i] - inventory[i + 1]) * (i + 1)\n",
    "                    ans = (ans + tmp) % (10 ** 9 + 7)\n",
    "                elif (inventory[i] - inventory[i + 1]) * (i + 1) == orders:\n",
    "                    return (ans + tmp) % (10 ** 9 + 7)\n",
    "                else:\n",
    "                    div, rem = orders // (i + 1), orders % (i + 1)\n",
    "                    ans = (ans + rem * (2 * inventory[i] - div) * (div + 1) // 2) % (10 ** 9 + 7)\n",
    "                    ans = (ans + (i + 1 - rem) * (2 * inventory[i] - div + 1) * div // 2) % (10 ** 9 + 7)\n",
    "                    return ans\n",
    "            else:\n",
    "                continue\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        n = len(inventory)\n",
    "\n",
    "        def check(k):\n",
    "            temp = sum([(inventory[i] - k) for i in range(n) if inventory[i]>k])\n",
    "            return temp>=orders\n",
    "\n",
    "        l,r = 0,max(inventory)\n",
    "        low = -1\n",
    "        while l<=r:\n",
    "            mid = (l+r)//2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "\n",
    "        buy_num = sum([(inventory[i] - low) for i in range(n) if inventory[i]>low])\n",
    "        cost = sum([(inventory[i]+low+1)*(inventory[i]-low)//2 for i in range(n) if inventory[i]>low])\n",
    "        diff = (buy_num - orders)*(low+1)\n",
    "        cost -= diff\n",
    "        return cost%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        if len(inventory) == 1:\n",
    "            return int(((inventory[0] + inventory[0] - orders + 1) * orders // 2)  % (10 ** 9 + 7))\n",
    "        inventory.sort(reverse=True)\n",
    "        inventory.append(0)\n",
    "        multi = 1\n",
    "        ans = 0\n",
    "        idx = 0\n",
    "        while orders > 0:\n",
    "            amount = inventory[idx] - inventory[idx+1]\n",
    "            if amount * multi < orders:\n",
    "                ans = (ans + ((inventory[idx] + inventory[idx+1]+ 1) * amount * multi) // 2) % (10 ** 9 + 7)\n",
    "                orders -= amount * multi\n",
    "                multi += 1\n",
    "                idx += 1\n",
    "            else:\n",
    "                t_amount = orders // multi\n",
    "                rest = orders % multi\n",
    "                ans = ans + ((inventory[idx] + inventory[idx] - t_amount + 1) * t_amount * multi) // 2\n",
    "                ans = (ans + rest * (inventory[idx] - t_amount)) % (10 ** 9 + 7)\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BinarySearch:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def find_int_left(low: int, high: int, check: Callable) -> int:\n",
    "        # 模板: 整数范围内二分查找，选择最靠左满足check\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid):\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid\n",
    "        return low if check(low) else high\n",
    "\n",
    "    @staticmethod\n",
    "    def find_int_right(low: int, high: int, check: Callable) -> int:\n",
    "        # 模板: 整数范围内二分查找，选择最靠右满足check\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        return high if check(high) else low\n",
    "\n",
    "    @staticmethod\n",
    "    def find_float_left(low: float, high: float, check: Callable, error=1e-6) -> float:\n",
    "        # 模板: 浮点数范围内二分查找, 选择最靠左满足check\n",
    "        while low < high - error:\n",
    "            mid = low + (high - low) / 2\n",
    "            if check(mid):\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid\n",
    "        return low if check(low) else high\n",
    "\n",
    "    @staticmethod\n",
    "    def find_float_right(low: float, high: float, check: Callable, error=1e-6) -> float:\n",
    "        # 模板: 浮点数范围内二分查找, 选择最靠右满足check\n",
    "        while low < high - error:\n",
    "            mid = low + (high - low) / 2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        return high if check(high) else low\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "\n",
    "        def check(w):\n",
    "            return sum(num-w for num in inventory if num >= w) <= orders\n",
    "\n",
    "        rest = BinarySearch().find_int_left(0, max(inventory), check)\n",
    "\n",
    "        mod = 10**9 + 7\n",
    "        ans = pre = 0\n",
    "        for num in inventory:\n",
    "            if num > rest:\n",
    "                pre += num-rest\n",
    "                ans += (rest+1+num)*(num-rest)//2\n",
    "        ans += (orders-pre)*rest\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        inventory.sort(reverse=True) #如果不reverse，就要从后往前遍历了\n",
    "        sell = 0\n",
    "        ans = 0\n",
    "\n",
    "        def get(start,cnt,repeat,times): #处理不满的一轮\n",
    "            ful,left = divmod(times,repeat)\n",
    "            #并列项数的整数倍部分按照等差数列求和公式，余数乘上卖出整数倍之后的价值\n",
    "            return (2*start-ful+1)*ful*repeat//2+(start-ful)*left \n",
    "\n",
    "        p = 0 \n",
    "        while p<len(inventory):\n",
    "            while p<len(inventory)-1 and inventory[p]==inventory[p+1]: #重复项合并处理\n",
    "                p+=1\n",
    "            #cnt为每种当前价值最高的球能卖出的数量，注意如果没有下一项，cnt就是当前项本身\n",
    "            cnt = inventory[p]-inventory[p+1] if p<len(inventory)-1 else inventory[p] \n",
    "\n",
    "            if (p+1)*cnt+sell<=orders: #注意数组的下标从0开始，所以并列价值最高的项数是p+1\n",
    "                #等差数列求和公式，尾项是是当前项减去cnt再加1，不要忘了乘上并列的数量\n",
    "                ans=(ans+(2*inventory[p]-cnt+1)*(p+1)*cnt//2)%(10**9+7) \n",
    "                sell+=(p+1)*cnt\n",
    "            else: \n",
    "                #这种情况对应这轮已经不满，这时可以直接return了\n",
    "                return (ans+get(inventory[p],cnt,p+1,orders-sell))%(10**9+7)\n",
    "            p+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        # 用于计算卖出矩形可以获得的价值\n",
    "        def calc_matrix(u: int, h: int, w: int) -> int:\n",
    "            return h * (u + u - h + 1) * w // 2\n",
    "\n",
    "        mod = 10 ** 9 + 7  # 定义模数\n",
    "        # 先排序 inventory，并添加一个0以便后续处理\n",
    "        inventory.append(0)\n",
    "        inventory.sort()\n",
    "        \n",
    "        self.count = 0  # 初始化总收益为0\n",
    "        now = len(inventory) - 1  # 设置当前指针到数组的最后一个元素\n",
    "        width = 1  # 初始化宽度为1\n",
    "        \n",
    "        # 主循环，贪心地选择卖出价值最大的球\n",
    "        while now > 0:\n",
    "            # 找到当前最高价值的球\n",
    "            while inventory[now - 1] == inventory[now]:\n",
    "                now -= 1\n",
    "                width += 1\n",
    "\n",
    "            # 设定上界和下界\n",
    "            upper = inventory[now]\n",
    "            lower = inventory[now - 1]\n",
    "            \n",
    "            # 判断是否可以卖出 (upper - lower) * width 这么多的球\n",
    "            if orders < (upper - lower) * width:\n",
    "                h = orders // width  # 计算还能卖多少高度\n",
    "                # 计算能获得的收益，并更新总收益\n",
    "                self.count += calc_matrix(upper, h, width) + ((orders - h * width) * (upper - h))\n",
    "                self.count %= mod\n",
    "                break\n",
    "            \n",
    "            # 如果可以卖出 (upper - lower) * width 这么多球，更新总收益\n",
    "            self.count += calc_matrix(upper, upper - lower, width)\n",
    "            self.count %= mod\n",
    "            \n",
    "            # 更新剩余订单和宽度\n",
    "            orders -= (upper - lower) * width\n",
    "            width += 1\n",
    "            now -= 1\n",
    "        \n",
    "        return self.count  # 返回总收益"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "\n",
    "        def check(ceil):\n",
    "            cnt = 0\n",
    "            for num in inventory:\n",
    "                if num > ceil:\n",
    "                    cnt += num - ceil\n",
    "            return cnt >= orders\n",
    "\n",
    "        # 确定卖之后剩余球的最大数量\n",
    "        low = 0\n",
    "        high = max(inventory)\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        rest = high if check(high) else low\n",
    "        rest += 1\n",
    "        \n",
    "        # 使用等差数列求和公式按照剩余的最大数量进行卖球\n",
    "        count = 0\n",
    "        ans = 0\n",
    "        for num in inventory:\n",
    "            if num > rest:\n",
    "                cur = num - rest\n",
    "                count += cur\n",
    "                ans += cur * (2 * rest + cur + 1) // 2\n",
    "                ans %= MOD\n",
    "\n",
    "        # 若还不够数量则加上这部分价值\n",
    "        ans += (orders - count) * rest\n",
    "        ans %= MOD\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        inventory.sort(reverse=True)\n",
    "        l, r = 0, inventory[0]\n",
    "        while l <= r:\n",
    "            m = l + r >> 1\n",
    "            tot = 0\n",
    "            for inv in inventory:\n",
    "                if inv < m:\n",
    "                    break\n",
    "                tot += inv - m\n",
    "            if tot > orders:\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "        tot = 0\n",
    "        ret = 0\n",
    "        tmp = l * (l + 1) // 2\n",
    "        for inv in inventory:\n",
    "            if inv < l:\n",
    "                break\n",
    "            tot += inv - l\n",
    "            ret += inv * (inv + 1) // 2 - tmp\n",
    "        d = orders - tot\n",
    "        return (ret + d * l) % 1000000007\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        if inventory is None:\n",
    "            return 0\n",
    "\n",
    "        if sum(inventory) < orders:\n",
    "            return -1\n",
    "        \n",
    "        if len(inventory) == 1:\n",
    "            return (inventory[0] + inventory[0] - orders + 1) * orders // 2 % 1000000007\n",
    "\n",
    "        inventory.sort(key = lambda x : -x)\n",
    "        # print(inventory)\n",
    "\n",
    "        t = None\n",
    "        i = 0\n",
    "        n = None\n",
    "        res = 0\n",
    "        tmp_res = None\n",
    "        while orders > 0:\n",
    "            t = i\n",
    "            num = inventory[t]\n",
    "            i += 1\n",
    "            while i < len(inventory) and inventory[i] == num:\n",
    "                i += 1\n",
    "            \n",
    "            n = orders // i\n",
    "            # print('-- * --' * 20)\n",
    "            # print(n, orders, i, t)\n",
    "            if i < len(inventory) and n >= inventory[t] - inventory[i]:\n",
    "                n = inventory[t] - inventory[i]\n",
    "                orders -= (n * i)\n",
    "                tmp_res = i * n * (inventory[t] + inventory[i] + 1) // 2\n",
    "                if tmp_res >= 1000000007:\n",
    "                    tmp_res %= 1000000007\n",
    "                res += tmp_res\n",
    "                if res >= 1000000007:\n",
    "                    res %= 1000000007\n",
    "            else:\n",
    "                orders -= (n * i)\n",
    "                tmp_res = i * n * (inventory[t] + (inventory[t] - n + 1)) // 2\n",
    "                if tmp_res >= 1000000007:\n",
    "                    tmp_res %= 1000000007\n",
    "                res += tmp_res\n",
    "                if res >= 1000000007:\n",
    "                    res %= 1000000007\n",
    "                \n",
    "                res += (orders * (inventory[t] - n))\n",
    "                if res >= 1000000007:\n",
    "                    res %= 1000000007\n",
    "                \n",
    "                orders = 0\n",
    "            # print(t, i, orders, tmp_res, res)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        # 二分查找 T 值\n",
    "        l, r, T = 0, max(inventory), -1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            total = sum(ai - mid for ai in inventory if ai >= mid)\n",
    "            if total <= orders:\n",
    "                T = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "\n",
    "        def range_sum(x, y):\n",
    "            return (x + y) * (y - x + 1) // 2\n",
    "        \n",
    "        rest = orders - sum(ai - T for ai in inventory if ai >= T)\n",
    "        ans = 0\n",
    "        for ai in inventory:\n",
    "            if ai >= T:\n",
    "                if rest > 0:\n",
    "                    ans += range_sum(T, ai)\n",
    "                    rest -= 1\n",
    "                else:\n",
    "                    ans += range_sum(T + 1, ai)\n",
    "                    \n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        mod=10**9+7\n",
    "        l,r,t=0,max(inventory),-1\n",
    "        while l<=r:\n",
    "            mid=(l+r)//2\n",
    "            total=sum(i-mid for i in inventory if i>=mid)\n",
    "            if total<orders:\n",
    "                t=mid\n",
    "                r=mid-1\n",
    "            else:\n",
    "                l=mid+1\n",
    "        rest=orders-sum(i-t for i in inventory if i>=t)\n",
    "        def ra(x,y):\n",
    "            return (x+y)*(y-x+1)//2\n",
    "        ans=0\n",
    "        for i in inventory:\n",
    "            if i>=t:\n",
    "                if rest>0:\n",
    "                    ans+=ra(t,i)\n",
    "                    rest-=1\n",
    "                else:\n",
    "                    ans+=ra(t+1,i)\n",
    "        return ans%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        # 二分查找 T 值\n",
    "        l, r, T = 0, max(inventory), -1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            total = sum(ai - mid for ai in inventory if ai >= mid)\n",
    "            if total <= orders:\n",
    "                T = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "\n",
    "        range_sum = lambda x, y: (x + y) * (y - x + 1) // 2\n",
    "        \n",
    "        rest = orders - sum(ai - T for ai in inventory if ai >= T)\n",
    "        ans = 0\n",
    "        for ai in inventory:\n",
    "            if ai >= T:\n",
    "                if rest > 0:\n",
    "                    ans += range_sum(T, ai)\n",
    "                    rest -= 1\n",
    "                else:\n",
    "                    ans += range_sum(T + 1, ai)\n",
    "                    \n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        def check(val):\n",
    "            # O(N)\n",
    "            total = 0\n",
    "            for i in inventory:\n",
    "                if i > val:\n",
    "                    total += i - val\n",
    "            return total\n",
    "\n",
    "        # O(N)\n",
    "        left, right = 0, max(inventory)\n",
    "\n",
    "        # 二分查找\n",
    "        # O(NlogN)\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid) >= orders:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "\n",
    "        # 计算销售临界值\n",
    "        sale_val = left\n",
    "\n",
    "        # 计算销售临界值的总量(不卖临界值的情况下)\n",
    "        sale_num = check(sale_val)\n",
    "\n",
    "        # 计算临界值之上的结果\n",
    "        ans = 0\n",
    "        for i in inventory:\n",
    "            if i > sale_val:\n",
    "                ans += (sale_val + 1 + i) * (i - sale_val) // 2\n",
    "                # print(i, \"->\", (sale_val + 1 + i) * (i - sale_val) // 2)\n",
    "\n",
    "        # 计算临界值的结果\n",
    "        ans += (orders - sale_num) * sale_val\n",
    "\n",
    "        # print(\"临界值:\", sale_val, sale_num)\n",
    "\n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        n=len(inventory)\n",
    "        mod=1000000007\n",
    "        inventory.sort(reverse=True)\n",
    "        def check(t):\n",
    "            cnt=0\n",
    "            for x in inventory:\n",
    "                if x>t:\n",
    "                    cnt+=x-t\n",
    "\n",
    "            return cnt>=orders\n",
    "        r=max(inventory)\n",
    "        l=0\n",
    "        while l<r-1:\n",
    "            mid=(l+r)//2\n",
    "            #mid=l+(r-l)//2\n",
    "            if check(mid):\n",
    "                l=mid\n",
    "            else:\n",
    "                r=mid \n",
    "        if check(r):\n",
    "            limit=r\n",
    "        else:\n",
    "            limit=l\n",
    "        itm=0\n",
    "        res=0\n",
    "        ans=0\n",
    "        limit=limit+1\n",
    "        count=0\n",
    "       #print(limit)\n",
    "       # print(inventory)\n",
    "        for x in inventory:\n",
    "            if x >limit:\n",
    "                cur =x-limit\n",
    "                count+=cur \n",
    "                ans=ans+(x+limit+1)*(x-limit)//2\n",
    "                #orders=orders-(x-limit)\n",
    "                #print(1,(((x+limit+1)*(x-limit))//2)%mod)\n",
    "          \n",
    "            #elif orders==0:\n",
    "              #  break\n",
    "            #print(ans)\n",
    "        ans += (orders - count) * limit\n",
    "        ans =ans% mod\n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n",
    "         \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 二分 + 贪心\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        # 二分查找 T 值\n",
    "        l, r, T = 0, max(inventory), -1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            total = sum(ai - mid for ai in inventory if ai >= mid)\n",
    "            if total <= orders:\n",
    "                T = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "\n",
    "        range_sum = lambda x, y: (x + y) * (y - x + 1) // 2\n",
    "        \n",
    "        rest = orders - sum(ai - T for ai in inventory if ai >= T)\n",
    "        ans = 0\n",
    "        for ai in inventory:\n",
    "            if ai >= T:\n",
    "                if rest > 0:\n",
    "                    ans += range_sum(T, ai)\n",
    "                    rest -= 1\n",
    "                else:\n",
    "                    ans += range_sum(T + 1, ai)\n",
    "                    \n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        # n = len(inventory)\n",
    "        # cnt = list(Counter(inventory).items())\n",
    "        # cnt.sort(reverse=True)\n",
    "        # print(cnt)\n",
    "        # ans, h = 0, 0\n",
    "        # for i, x in enumerate(cnt):\n",
    "        #     k, v = x\n",
    "        #     h += v\n",
    "        #     if i+1 < n and orders < (cnt[i][0] - cnt[i+1][0]) * h:\n",
    "        #         break\n",
    "        #     orders -= (cnt[i][0] - cnt[i+1][0]) * h\n",
    "        #     ans += (cnt[i][0]+cnt[i+1][0]+1) * (cnt[i][0]-cnt[i+1][0]) // 2 * h\n",
    "        # mx = cnt[i][0]\n",
    "        # while orders >= h:\n",
    "        #     orders -= h\n",
    "        #     ans += mx * h\n",
    "        #     mx -= 1\n",
    "        # return ans + orders * mx\n",
    "\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        # 二分查找 T 值\n",
    "        l, r, T = 0, max(inventory), -1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            total = sum(ai - mid for ai in inventory if ai >= mid)\n",
    "            if total <= orders:\n",
    "                T = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "\n",
    "        range_sum = lambda x, y: (x + y) * (y - x + 1) // 2\n",
    "        \n",
    "        rest = orders - sum(ai - T for ai in inventory if ai >= T)\n",
    "        ans = 0\n",
    "        for ai in inventory:\n",
    "            if ai >= T:\n",
    "                if rest > 0:\n",
    "                    ans += range_sum(T, ai)\n",
    "                    rest -= 1\n",
    "                else:\n",
    "                    ans += range_sum(T + 1, ai)\n",
    "                    \n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        '''\n",
    "        有一个值T，满足当 inventory[i] >=T时，会有 T 或 T - 1 次被去除；\n",
    "        且对于所有大于T的的元素 sum( inventory[i] - T ) < order < sum( inventory[i] - T +1)。\n",
    "        所以，可以通过二分查找找到数值T。\n",
    "\n",
    "        对于 order - sum( inventory[i] - T ) 个球，他们的得分都是都是 T\n",
    "\n",
    "        '''\n",
    "\n",
    "        mod=10**9+7\n",
    "\n",
    "        l,r,T = 0,max(inventory),-1\n",
    "\n",
    "        while l<=r:\n",
    "            mid=(l+r)//2\n",
    "            total = sum( ai - mid   for ai in inventory if ai>=mid )\n",
    "            if total <= orders:\n",
    "                T=mid  #保留最接近的T值，此时，total <=orders\n",
    "                r=mid-1\n",
    "            else:\n",
    "                l=mid+1\n",
    "\n",
    "        rest = orders - sum(ai - T  for ai in inventory if ai>=T)\n",
    "        ans=0\n",
    "\n",
    "        range_sum = lambda x, y: (x + y) * (y - x + 1) // 2\n",
    "\n",
    "\n",
    "        for ai in inventory:\n",
    "            if ai>T:\n",
    "                ans+=range_sum(T+1,ai)\n",
    "        #     print(ai, T, ans)\n",
    "        # print(ans,rest)\n",
    "\n",
    "        if rest>0:\n",
    "            ans += rest*T\n",
    "\n",
    "        return ans % mod\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        '''\n",
    "        有一个值T，满足当 inventory[i] >=T时，会有 T 或 T - 1 次被去除；\n",
    "        且对于所有大于T的的元素 sum( inventory[i] - T ) < order < sum( inventory[i] - T +1)。\n",
    "        所以，可以通过二分查找找到数值T。\n",
    "\n",
    "        对于 order - sum( inventory[i] - T ) 个球，他们的得分都是都是 T\n",
    "\n",
    "        '''\n",
    "\n",
    "        mod=10**9+7\n",
    "\n",
    "        l,r,T = 0,max(inventory),-1\n",
    "\n",
    "        while l<=r:\n",
    "            mid=(l+r)//2\n",
    "            total = sum( ai - mid   for ai in inventory if ai>=mid )  # ai - mid的意思表示，最终不包含mid本身，e.g.5-3，表示取5、4两个值。\n",
    "            if total <= orders:\n",
    "                T=mid  #保留最接近的T值，此时，total <=orders\n",
    "                r=mid-1\n",
    "            else:\n",
    "                l=mid+1\n",
    "            # print(total,orders,T)\n",
    "        rest = orders - sum(ai - T  for ai in inventory if ai>T)\n",
    "        ans=0\n",
    "\n",
    "        range_sum = lambda x, y: (x + y) * (y - x + 1) // 2\n",
    "        for ai in inventory:\n",
    "            if ai>T:\n",
    "                ans+=range_sum(T+1,ai)\n",
    "        if rest>0: # 剩余部分，价值都是T\n",
    "            ans += rest*T\n",
    "\n",
    "        return ans % mod\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        low = 0\n",
    "        high = max(inventory)\n",
    "        n = len(inventory)\n",
    "        while low < high:\n",
    "            mid = (low + high) // 2\n",
    "            temp = 0\n",
    "            for i in range(n):\n",
    "                temp += max(inventory[i] - mid, 0)\n",
    "            if temp >= orders:\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid\n",
    "\n",
    "        ans = 0\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            ans += max(0, (low + 1 + inventory[i]) * (inventory[i] - low) // 2)\n",
    "            count += max(inventory[i] - low, 0)\n",
    "        ans += (orders - count)*low\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        # 二分查找 T 值\n",
    "        l, r, T = 0, max(inventory), -1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            total = sum(ai - mid for ai in inventory if ai >= mid)\n",
    "            if total <= orders:\n",
    "                T = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "\n",
    "        range_sum = lambda x, y: (x + y) * (y - x + 1) // 2\n",
    "        \n",
    "        rest = orders - sum(ai - T for ai in inventory if ai >= T)\n",
    "        ans = 0\n",
    "        for ai in inventory:\n",
    "            if ai >= T:\n",
    "                if rest > 0:\n",
    "                    ans += range_sum(T, ai)\n",
    "                    rest -= 1\n",
    "                else:\n",
    "                    ans += range_sum(T + 1, ai)\n",
    "                    \n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        '''\n",
    "        有一个值T，满足当 inventory[i] >=T时，会有 T 或 T - 1 次被去除；\n",
    "        且对于所有大于T的的元素 sum( inventory[i] - T ) < order < sum( inventory[i] - T +1)。\n",
    "        所以，可以通过二分查找找到数值T。\n",
    "\n",
    "        对于 order - sum( inventory[i] - T ) 个球，他们的得分都是都是 T\n",
    "\n",
    "        '''\n",
    "\n",
    "        mod=10**9+7\n",
    "\n",
    "        l,r,T = 0,max(inventory),-1\n",
    "\n",
    "        while l<=r:\n",
    "            mid=(l+r)//2\n",
    "            total = sum( ai - mid   for ai in inventory if ai>=mid )  # ai - mid的意思表示，最终不包含mid本身，e.g.5-3，表示取5、4两个值。\n",
    "            if total <= orders:\n",
    "                T=mid  #保留最接近的T值，此时，total <=orders\n",
    "                r=mid-1\n",
    "            else:\n",
    "                l=mid+1\n",
    "            # print(total,orders,T)\n",
    "        rest = orders - sum(ai - T  for ai in inventory if ai>T)\n",
    "        ans=0\n",
    "\n",
    "        range_sum = lambda x, y: (x + y) * (y - x + 1) // 2   #整除与否都不重要，这里必然是整数\n",
    "        for ai in inventory:\n",
    "            if ai>T:\n",
    "                ans+=range_sum(T+1,ai)\n",
    "        if rest>0: # 剩余部分，价值都是T\n",
    "            ans += rest*T\n",
    "\n",
    "        return ans % mod\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        ball_dict = collections.defaultdict(int)\n",
    "        for num in inventory:\n",
    "            ball_dict[num] += 1\n",
    "        ball_list = list(ball_dict.keys())\n",
    "        ball_list.sort()\n",
    "        ans = 0\n",
    "        while orders > 0:\n",
    "            tmp = ball_list.pop()\n",
    "            num = ball_dict[tmp]\n",
    "            if not len(ball_list) or (tmp - ball_list[-1]) * num >= orders:\n",
    "                chushu = orders // num\n",
    "                yushu = orders % num\n",
    "                ans = (ans + (tmp * 2 - chushu + 1) * chushu * num // 2 + yushu * (tmp - chushu)) % (10 ** 9 + 7)\n",
    "                orders = 0\n",
    "            else:\n",
    "                next_tmp = ball_list[-1]\n",
    "                ans = (ans + (tmp + next_tmp + 1) * (tmp - next_tmp) // 2 * num) % (10 ** 9 + 7)\n",
    "                orders -= (tmp - next_tmp) * num\n",
    "                ball_dict[next_tmp] += num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        h = []\n",
    "        mod = 10 ** 9 + 7\n",
    "        dic = dict(Counter(inventory))\n",
    "        dic[0] = 0\n",
    "        keys = list(dic.keys())\n",
    "        keys.sort(reverse=True)\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(len(keys)-1) :\n",
    "            n1 = dic[keys[i]]\n",
    "            a1 = keys[i]\n",
    "            a2 = keys[i+1] + 1\n",
    "            if orders <= (a1 - a2 + 1) * n1 :\n",
    "                d, m = divmod(orders, n1)\n",
    "                ans += (((a1 + a1 - d + 1) * d * n1) // 2) % mod\n",
    "                ans += ((a1 - d) * m) % mod\n",
    "                break\n",
    "            else :\n",
    "                d = min(orders, (a1 - a2 + 1) * dic[keys[i]])\n",
    "                ans += (((a1 + a2) * (a1 - a2 + 1) * n1) // 2) % mod\n",
    "                dic[a2-1] += dic[a1]\n",
    "            orders -= ((a1 - a2 + 1) * n1)\n",
    "\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        \n",
    "        cnt = Counter(inventory)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        a = sorted(cnt.items(), reverse=True)\n",
    "        a.append((0, 0))\n",
    "        n = len(a)\n",
    "        left = orders\n",
    "        ans = 0\n",
    "        for i in range(n - 1):\n",
    "            k, v = a[i]\n",
    "            c = cnt[k]\n",
    "            nk, _ = a[i + 1]\n",
    "            if left >= (k - nk) * c:\n",
    "                tot = (nk + 1 + k) * (k - nk) * c // 2\n",
    "                cnt[nk] += c\n",
    "                left -= (k - nk) * c\n",
    "                ans += tot\n",
    "            else:\n",
    "                diff, mod = left // c, left % c\n",
    "                # print(ans, k, c, left, diff, mod)\n",
    "                # print(k - diff + 1, k, (k - diff + 1 + k) * diff * (c - mod) // 2 , (k - diff + k) * (diff + 1) * mod // 2)\n",
    "                tot = (k - diff + 1 + k) * diff * (c - mod) // 2  + (k - diff + k) * (diff + 1) * mod // 2\n",
    "                ans += tot\n",
    "                left = 0\n",
    "            if not left:\n",
    "                break\n",
    "        return ans % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        cnt = []\n",
    "        for k,v in Counter(inventory).items():\n",
    "            cnt.append([k,v])\n",
    "        cnt.sort(key = lambda x: x[0])\n",
    "        ans = 0\n",
    "        while orders:\n",
    "            k,v = cnt.pop()\n",
    "            if cnt:\n",
    "                # 当前v个k都可以缩减到cnt[-1][0]\n",
    "                if orders >= v * (k - cnt[-1][0]):\n",
    "                    orders  -= v * (k - cnt[-1][0])\n",
    "                    ans += (k - cnt[-1][0]) * (cnt[-1][0] + 1 + k) // 2 * v\n",
    "                    cnt[-1][1] += v\n",
    "                    continue\n",
    "            \n",
    "            t = orders // v     # 每个k最多可以缩减t次\n",
    "            m = orders - t * v  # 每个k缩减t次后剩余m个 这时m肯定小于 v\n",
    "            ans += (t) * (k + 1 - t + k) // 2 * v   # v个k缩减t次求和\n",
    "            t = k - t   # v个k缩减t次后的值\n",
    "            ans += m * t    # 剩余的m也要算上 (m < v)\n",
    "            orders = 0\n",
    "        return ans % int(1e9+7)\n",
    "s = Solution()\n",
    "s.maxProfit([2,5],4)\n",
    "        \n",
    "# end-------------------------------------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def maxProfit(self, inventory: List[int], orders: int) -> int:\n",
    "        cnt = []\n",
    "        for k,v in Counter(inventory).items():\n",
    "            cnt.append([k,v])\n",
    "        cnt.sort(key = lambda x: x[0])\n",
    "        ans = 0\n",
    "        while orders:\n",
    "            k,v = cnt.pop()\n",
    "            if cnt:\n",
    "                if orders >= v * (k - cnt[-1][0]):\n",
    "                    orders  -= v * (k - cnt[-1][0])\n",
    "                    ans += (k - cnt[-1][0]) * (cnt[-1][0] + 1 + k) // 2 * v\n",
    "                    cnt[-1][1] += v\n",
    "                    continue\n",
    "            t = orders // v\n",
    "            m = orders - t * v\n",
    "            ans += (t) * (k + 1 - t + k) // 2 * v\n",
    "            t = k - t\n",
    "            ans += m * t\n",
    "            orders = 0\n",
    "\n",
    "\n",
    "        return ans % int(1e9+7)\n",
    "s = Solution()\n",
    "s.maxProfit([2,5],4)\n",
    "        \n",
    "# end-------------------------------------------------------"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
